1. Technical Field
The present invention relates to the field of tomography and, in particular, to the reconstruction of images from emission tomography of microscopic samples, for example, as applied to the internal structure of semiconductors. A non-linear programming algorithm, known as the expectation/maximization (EM) algorithm, is bounded and applied to the solution of the data recovered by discrete emission tomography to reproduce an image for display.
2. Description of the Relevant Art
U.S. Pat. No. 5,659,175, to Fishburn et al. describes apparatus and a method for tomography of microscopic samples. For example, let S be a finite subset of a lattice Z and let  be a finite collection of subsets of Z. For each Lxcex5, let v(L) be the number of points in L∩S. Fishburn et al. recognized that the integer programming problem could be translated into a problem involving fuzzy sets that can be solved using linear programming. The problem of reconstructing the set S from knowledge of {v(L); Lxcex5} when  is a collection of lines in Z in the main directions (the subject of discrete tomography and lines in main directions will be further described herein) is also considered. The approach in the ""175 patent is based on (a) relaxing the constraint that S be a set to requiring that S be a fuzzy set, and (b) using a linear program to find a feasible fuzzy set. From a practical point of view (a) amounts to replacing                                           v            ⁡                          (              L              )                                =                                    ∑                              z                ∈                Z                                      ⁢                                                            X                  S                                ⁡                                  (                  z                  )                                            ⁢                                                X                  L                                ⁡                                  (                  z                  )                                                                    ,                  xe2x80x83                ⁢                  L          ∈          ℒ                                    (1.1)            
where XA denotes the indicator function of a set A, with                                           v            ⁡                          (              L              )                                =                                    ∑                              z                ∈                Z                                      ⁢                                          f                ⁡                                  (                  z                  )                                            ⁢                                                X                  L                                ⁡                                  (                  z                  )                                                                    ,                  xe2x80x83                ⁢                  L          ∈          ℒ                ,                  xe2x80x83                ⁢                  0          ≤                      f            ⁡                          (              z              )                                ≤          1                ,                  xe2x80x83                ⁢                  z          ∈          Z                                    (1.2)            
and (b) amounts to finding a feasible solution in f(z), zxcex5Z, for the constrained linear system (ii), using linear programming. The approach has important scientific applications in high-resolution electron-microscopy of crystals.
The problem of reconstructing an image for display from probabilities of occupancy of individual lattice sites within a crystal is described by the ""175 patent in some detail, but some of the discussion is repeated here with reference to FIGS. 7-14 which correspond to FIGS. 1-7 and 13 of the ""175 patent. In tomographic radiography, projection radiography is done to capture the amount of attenuation of a beam as it passes through an object as a black level but repeated many times. The repetitions produce a collection of data which is used to generate an image of the cross section of an object. That is, multiple xe2x80x9cside viewsxe2x80x9d of the object are used to generate a cross sectional view called a phantom.
Referring first to FIG. 7, some of the basic principles of tomography will be briefly described. The object xe2x80x9c3xe2x80x9d under scan of FIG. 7A is conceptually divided into pixels P, as in FIG. 7B. Each ray R of radiation passing through the body of object xe2x80x9c3xe2x80x9d is attenuated by the sequence of pixels through which it passes according to the attenuation coefficient of each pixel, unknown in real-life except when the imaged object is an experimental xe2x80x9cphantomxe2x80x9d. A collection of parallel rays, spanning from point C to point D, produces one of the projection images. The amount of attenuation of each ray is measured using a detector for producing a numerical output. Then, an equation is derived for each ray. A simplified example is given by FIG. 7C.
If the initial intensity of the ray is Io, and if the intensity of the ray after passing through the object is If then Equation (1) is obtained for FIG. 7C:
If=[Ioexe2x88x92xcex11L1][exe2x88x92xcex12L2][exe2x88x92xcex13L3]xe2x80x83xe2x80x83(1)
Each bracketed term in equation (1) corresponds to a position indicated in FIG. 7C.
Equation (1) results from a single ray. Since multiple rays produce each image, multiple equations are obtained for each image. Further, since numerous images are obtained, numerous sets of equations, each containing multiple equations, are obtained.
The numerous sets, of multiple equations each, are solved for the attenuation variables xcex1, three of which are found in Equation (1). Each xcex1 represents the attenuation coefficient of a pixel.
After a solution is obtained, the resulting attenuation variable, xcex1, for each pixel is mapped graphically, for example, by using darker colors for larger coefficients and lighter colors for smaller coefficients. The map obtained from this process is commonly called a reconstruction phantom. Since the attenuation coefficient of each pixel can be correlated with other physical parameters associated with the pixel, such as density (mass per unit volume), the mapping indicates the density pattern (or other parameter) within the phantom.
This type of tomography is called xe2x80x9ccontinuous domain,xe2x80x9d because values of the attenuation coefficients in the pixels are continuous, and pixelization can be made infinitesimally fine. Discrete domain tomography relates to ascertaining the presence or absence of objects by a single binary variable when the objects may be smaller than the beam irradiating them. Briefly, and according to the ""175 patent, line counts are obtained from the crystal lattice under radiation representing the number of atoms in a specific row or line. A system of equations is derived from the line counts as described by the ""175 patent and a solution obtained. Referring to FIG. 13A, the count of atoms in column C1 (which is a line) is five. The line count of five produces the equation:
X11+X21+X31+X41+X51+X61=line count=5
In the equations, a value of xe2x80x9c1xe2x80x9d for an xe2x80x9cXxe2x80x9d indicates the presence of an atom and a value of xe2x80x9c0xe2x80x9d represents the absence. Then, a system of multiple equations is obtained from the multiple line counts that are solved by linear programming processes according to the ""175 patent.
Detailed procedures for obtaining line counts are known in the art. One procedure is described in xe2x80x9cMapping Projected Potential, Interfacial Roughness, and Composition in General Crystalline Solids by Quantitative Electron Microscopy,xe2x80x9d by P. Schwander et al., Phys. Rev. Lett., 71, pp 4150-4153 (1993).
Referring to FIG. 8, a small sample 30 of a crystal is positioned in an electron beam 33 output by a transmission electron microscope, TEM. A detector detects the beam, and one can make inferences of physical features of the sample 30. The Sample 30 of the ""175 patent measured approximately 100 by 100 atoms in cross section. Larger samples in cross section, for example, 1000 atoms by 1000 atoms, and three dimensional samples, for example, slices of crystals of a size 25xc3x971000xc3x971000 atoms can also be analyzed. An expander 36 expands beam 33. A detector 39 is, for example, a photographic film. The distance D is measurable by the human eye. When the beam 33 passes through an atom 5, a relatively faint spot is produced on film 39. When the beam passes through four atoms, the spot density may be intermediate in intensity, and so on. A ray 6 may encounter no atoms and produces no darkening. The gray levels of all spots are quantified and plotted producing a plot 42 (FIG. 12). The electron beam 33 is moved horizontally across the sample at radius R per FIG. 9.
The plot 42 can be made linear (although discrete) and of the form: y=mx+b, where y is the number of atoms, x is the grey scale value, m is the slope of a line (Delta) and b is the y-intercept. Correlations between grey scale level and number of atoms in a column are used in performing tomography on sample 30. Complex patterns can be found as in FIG. 11 and linear plots formed as in FIG. 12 or the sample may be rotated as in FIG. 10 all to the result that linear programming processes may be mathematically applied to the detected line count data to obtain a reconstruction of the illuminated object 30. For example, as between FIG. 13A and 13B the sample may be rotated 90 degrees, FIG. 13B showing the new position. The data from FIG. 13 allows a set of equations to be derived as described by the ""175 patent where each x of a matrix set of equations shows the absence or presence of atoms. The constraint that is applied is that the variables xe2x80x9cxxe2x80x9d are limited to between 0 and 1. The ""175 patent shows three reconstructed xe2x80x9cphantomsxe2x80x9d FIGS. 9B, 10B and 11B from simulated cross sections FIGS. 9A, 10A and 11A which may be compared with the results of applying the non-linear programming algorithm of the present invention shown in FIGS. 1-6.
The present invention applies an Expectation/Maximization algorthm (EM) processes to improve the reconstruction of images from high resolution electron microscopes. According to the principles of the present invention, a method of obtaining probabilities of occupancy of lattice sites in a sample comprises the steps of obtaining line count data and obtaining the probabilities of occupancy of the lattice sites from the line count data by non-linear programming processes, in particular, by applying the expectation/maximization algorithm bounded by the upper bound constraint that each variable is valued at less than or equal to one. The application of the non-linear programming process can obtain a phantom in 30,000 or fewer iterations and in real time (less than 4 seconds) of the EM algorithm for the exemplary phantoms of the ""175 patent.
Apparatus for discrete tomography comprises a means for irradiating a sample, means for producing line count data of atoms of the irradiated sample and means for deriving a tomographic phantom from the line count data comprising a processor for applying a non-linear programming algorithm to the line count data to obtain probabilities of occupancy of lattice sites in the sample.
Further advantages and features of the present invention will be understood from the following detailed description of the present invention.